package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode0287 
* @author      : ganwei 
* @date        : 2020年5月23日 
* @Description : 287. 寻找重复数 
*/
public class Leetcode0287 {
	/**
	 * -寻找重复整数，暴力，速度太慢了。
	 */
    public int findDuplicate(int[] nums) {
    	int n = nums.length;
    	for(int i = 0; i < n; i++) {
    		for(int j = i+1; j < n; j++) {
    			if(nums[i] == nums[j]) {
    				return nums[i];
    			}
    		}
    	}
    	return 0;
    }
    /**
     * -弗洛伊德的乌龟和兔子（循环检测）
     */
    public int findDuplicate_1(int[] nums) {
        int tortoise = nums[0];
        int hare = nums[0];
        
        do {
        	tortoise = nums[tortoise];
        	hare = nums[nums[hare]];
        }while(tortoise != hare);
        	
        int ptr1 = nums[0];
        int ptr2 = tortoise;
        while(ptr1 != ptr2) {
        	ptr1 = nums[ptr1];
        	ptr2 = nums[ptr2];
        }
        
    	return ptr1;
    }
    
    public static void main(String[] args) {
    	
    }
}
